package leetcode

//https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/

// maxChunksToSorted 计算将数组分割成多少个块（chunks），使得每个块内部排序后，整个数组依然有序。
// 参数 arr 是一个整数数组。
func maxChunksToSorted(arr []int) int {
	// 获取数组长度
	n := len(arr)
	// 初始化一个辅助数组，用于存储从右向左的最小值
	minHelper := make([]int, n)

	// 从右向左遍历数组，初始化minHelper数组
	minHelper[n-1] = arr[n-1]
	for i := n - 2; i >= 0; i-- {
		// 更新minHelper数组，保证minHelper[i]是arr[i]到arr[n-1]中的最小值
		if arr[i] < minHelper[i+1] {
			minHelper[i] = arr[i]
		} else {
			minHelper[i] = minHelper[i+1]
		}
	}

	// 初始化结果变量为1，表示至少有一个块
	res := 1
	// 初始化一个辅助变量，用于存储从左向右的最大值
	maxHelper := arr[0]

	// 从左向右遍历数组，确定可以形成多少个块
	for i := 1; i < n; i++ {
		// 如果当前索引处的minHelper值大于maxHelper，说明可以形成一个新的块
		if minHelper[i] >= maxHelper {
			res++
		}

		// 更新maxHelper，保证maxHelper是arr[0]到arr[i]中的最大值
		if arr[i] > maxHelper {
			maxHelper = arr[i]
		}
	}
	// 返回可以形成的块的数量
	return res
}
